package org.test.analysis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;


/**
 * 图。。。。
 * @author game
 *
 */
public class fivepointtwo {

	public static void main(String arg[]) {

		Graph graph = new Graph();

		Vertex v0 = new Vertex("a");
		Vertex v1 = new Vertex("b");
		Vertex v2 = new Vertex("c");
		Vertex v3 = new Vertex("d");
		Vertex v4 = new Vertex("e");
		Vertex v5 = new Vertex("f");

		graph.addVertext(v0);
		graph.addVertext(v1);
		graph.addVertext(v2);
		graph.addVertext(v3);
		graph.addVertext(v4);

		graph.addVertext(v5);

		graph.addEdge(0, 2);
		graph.addEdge(0, 1);
		graph.addEdge(0, 3);
		graph.addEdge(1, 3);
		graph.addEdge(3, 4);

		// graph.displayGraph();
		graph.dfs();
		graph.bfs();

	}
}

class Graph {

	private final int MAX_VERTS = 20;

	private Vertex vertexList[];

	private int adjMat[][];

	private int nVerts;// 当前顶点数

	public Graph() {
		vertexList = new Vertex[MAX_VERTS];
		adjMat = new int[MAX_VERTS][MAX_VERTS];
		nVerts = 0;
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				adjMat[i][j] = 0;
			}
		}
	}

	/**
	 * 增加点
	 * 
	 * @param vertex
	 */
	public void addVertext(Vertex vertex) {
		vertexList[nVerts++] = vertex;
	}

	/**
	 * 增加边
	 * 
	 * @param start
	 * @param end
	 */
	public void addEdge(int start, int end) {
		adjMat[start][end] = 1;
		adjMat[end][start] = 1;
	}

	/**
	 * 
	 * @param v
	 */
	public void displayGraph(int v) {
		System.out.println(vertexList[v]);
	}

	/**
	 * 显示所有的
	 */
	public void displayGraph() {
		// 打印点
		for (int i = 0; i < nVerts; i++) {
			displayGraph(i);
		}
		// 打印边
		for (int i = 0; i < MAX_VERTS; i++) {
			for (int j = 0; j < MAX_VERTS; j++) {
				if ((adjMat[i][j] == 1) && (i <= j)) {
					System.out.println("点" + vertexList[i] + "和点"
							+ vertexList[j] + "有连接");
				}
			}
		}
	}

	/**
	 * 通过v找下一个 返回-1说明没有下一个元素了。
	 * 
	 * 
	 * @param v
	 */
	public int getAdjUnvisitedVertex(int v) {

		for (int i = 0; i < nVerts; i++) {

			if (adjMat[v][i] == 1) { // 是下一个点
				if (!vertexList[i].isVisited()) {// 未访问
					return i;
				}
			}
		}
		return -1;
	}

	/**
	 * v以下的点,由于这个函数完成后没有resetvisted，所以，要private
	 * 
	 * @param v
	 */
	private void dfs(int v) {

		displayGraph(v);
		vertexList[v].setVisited(true);// 设为真

		for (int i = 0; i < nVerts; i++) {
			int nextV = getAdjUnvisitedVertex(v);
			if (nextV == -1) {// 没有下一个元素了。
				System.out.println("当前的元素为" + vertexList[v] + ",没有未访问的元素了");
				return;
			}
			dfs(nextV);
		}
	}

	/**
	 * 这个图的遍历
	 */
	public void dfs() {
		for (int i = 0; i < nVerts; i++) {
			if (!vertexList[i].isVisited()) {
				dfs(i);
			}
		}
		this.resetVisited();
	}

	/**
	 * 这个图的遍历
	 */
	public void bfs() {
		for (int i = 0; i < nVerts; i++) {
			if (!vertexList[i].isVisited()) {
				bfs(i);
			}
		}
		this.resetVisited();
	}

	/**
	 * 由于这个函数完成后没有resetvisted，所以，要private
	 * 
	 * @param v
	 */
	private void bfs(int v) {

		Queue<Integer> vertQueue = new LinkedList<Integer>();
		int v1;
		int v2;

		displayGraph(v);
		vertexList[v].setVisited(true);

		while ((v2 = getAdjUnvisitedVertex(v)) != -1) {// 有子孙元素
			vertQueue.add(v2);
			vertexList[v2].setVisited(true);
		}

		while (vertQueue.peek() != null) { // 不为空
			v1 = vertQueue.poll();

			displayGraph(v1);

			while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
				vertQueue.add(v2);
				vertexList[v2].setVisited(true); // 这个循环其实是查找，不过要setvisited才能循环。所以上面的displayG下面不用去set了.这样的设计是否有问题？？？
			}
		}
	}

	/**
	 * 把所有节点重回
	 */
	public void resetVisited() {
		for (int i = 0; i < nVerts; i++) {
			vertexList[i].setVisited(false);
		}
	}

}

/**
 * 点
 * 
 * @author game
 * 
 */
class Vertex {

	private Object label;// 点的标志

	private boolean visited;

	public Vertex(Object label) {
		this.label = label;
		this.visited = false;
	}

	public Object getLabel() {
		return label;
	}

	public void setLabel(Object label) {
		this.label = label;
	}

	public boolean isVisited() {
		return visited;
	}

	public void setVisited(boolean visited) {
		this.visited = visited;
	}

	@Override
	public String toString() {
		return "Vertex [label=" + label + "]";
	}

}